package dynamic;

public class EggDrop {

  public static int eggDrop(int n, int k)
  {
      /* A 2D table where entery eggFloor[i][j] will represent minimum
         number of trials needed for i eggs and j floors. */
      int eggFloor[][] = new int[n+1][k+1];
      int res;
      int i, j, x;
   
      // We need one trial for one floor and0 trials for 0 floors
      for (i = 1; i <= n; i++)
      {
          eggFloor[i][1] = 1;
          eggFloor[i][0] = 0;
      }
   
      // We always need j trials for one egg and j floors.
      for (j = 1; j <= k; j++)
          eggFloor[1][j] = j;
   
      // Fill rest of the entries in table using optimal substructure
      // property
      for (i = 2; i <= n; i++)
      {
          for (j = 2; j <= k; j++)
          {
              eggFloor[i][j] = Integer.MAX_VALUE;
              for (x = 1; x <= j; x++)
              {
                  res = 1 + Math.max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
                  if (res < eggFloor[i][j])
                      eggFloor[i][j] = res;
              }
          }
      }
   
      // eggFloor[n][k] holds the result
      return eggFloor[n][k];
  }
  
  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(eggDrop(2,100));
  }

}
